#include <iostream>
#include "backtracking.h"

void test1() {
    BackTracking backtracking;
    std::vector<int> nums = {0,7,3,4,8,7,19};
    TreeNode* root = backtracking.CreatTree(nums,0);
    // backtracking.printTree(root);
    // backtracking.preOrderWith7(root);
    
    std::vector<int> path;
    std::vector<std::vector<int>> res;
    // backtracking.preOrderWith7path(root,path,res);
    backtracking.preOrderWith7pathNo3(root,path,res);
    for(int i = 0; i < res.size();i++) {
        for(int j = 0;j < res.at(i).size();j++) {
            std::cout << res.at(i).at(j) << " ";
        }
            std::cout << " " << std::endl;
    }

    backtracking.freeTree(root);
    return;
}

// 全排列问题，无相等元素的情况
void permutationI() {
    std::vector<int> nums = {1,2,3};
    std::vector<int> state;
    std::vector<bool> selected(nums.size(),false);
    std::vector<std::vector<int>> res;
    BackTracking backtracking;
    backtracking.backtrackingforPermutationsI(state,nums,selected,res);
    for(int i = 0; i < res.size();i++) {
        for(int j = 0;j < res.at(i).size();j++) {
            std::cout << res.at(i).at(j) << " ";
        }
            std::cout << " " << std::endl;
    }
    return;
}

// 全排列问题，存在相等元素的情况
void permutationII() {
    std::vector<int> nums = {1,1,3};
    std::vector<int> state;
    std::vector<bool> selected(nums.size(),false);
    std::vector<std::vector<int>> res;
    BackTracking backtracking;
    backtracking.backtrackingforPermutationsII(state,nums,selected,res);
    for(int i = 0; i < res.size();i++) {
        for(int j = 0;j < res.at(i).size();j++) {
            std::cout << res.at(i).at(j) << " ";
        }
            std::cout << " " << std::endl;
    }
    return;
}

// 子集和问题，不考虑重复元素，存在重复子集的解法
void SubSetSumINaive() {
    std::vector<int> nums = {3,4,5};
    std::vector<int> state;
    int target = 9;
    std::vector<std::vector<int>> res;
    BackTracking backtracking;
    backtracking.backtrackingforSubSetSumINaive(state,nums,0,target,res);
    for(int i = 0; i < res.size();i++) {
        for(int j = 0;j < res.at(i).size();j++) {
            std::cout << res.at(i).at(j) << " ";
        }
            std::cout << " " << std::endl;
    }
    return;
}

// 子集和问题，不考虑重复元素，不存在重复子集的解法
void SubSetSumI() {
    std::vector<int> nums = {3,4,5};
    std::vector<int> state;
    int target = 9;
    
    std::vector<std::vector<int>> res;
    BackTracking backtracking;
    backtracking.backtrackingforSubSetSumI(state,nums,target,0,res);
    for(int i = 0; i < res.size();i++) {
        for(int j = 0;j < res.at(i).size();j++) {
            std::cout << res.at(i).at(j) << " ";
        }
            std::cout << " " << std::endl;
    }
    return;
}

// 子集和问题，存在重复元素，不存在重复子集的解法
void SubSetSumII() {
    std::vector<int> nums = {4,4,5};
    std::vector<int> state;
    int target = 9;
    std::vector<std::vector<int>> res;
    BackTracking backtracking;
    backtracking.backtrackingforSubSetSumII(state,nums,target,0,res);
    for(int i = 0; i < res.size();i++) {
        for(int j = 0;j < res.at(i).size();j++) {
            std::cout << res.at(i).at(j) << " ";
        }
            std::cout << " " << std::endl;
    }
    return;
}

// N皇后问题
void nQueens(int n) {
    std::vector<std::vector<std::vector<std::string>>> res;
    std::vector<std::vector<std::string>> state(n,std::vector<std::string>(n,"#")); // "Q"表示放置皇后，"#"表示不放置
    std::vector<bool> cols(n,false);
    std::vector<bool> diags1(2 * n - 1,false);
    std::vector<bool> diags2(2 * n - 1,false);
    for(int i = 0; i < state.size();i++) {
        for(int j = 0;j < state.at(i).size();j++) {
            std::cout << state.at(i).at(j) << " ";
        }
    std::cout << "\n";
    }
    BackTracking backtracking;
    backtracking.backtrackingfornQueens(0,n,state,cols,diags1,diags2,res);
    std::cout << "res.size(): " << res.size() << std::endl;
    for(int i = 0; i < res.size();i++) {
        for(int j = 0;j < res.at(i).size();j++) {
            for(int k = 0;k < res.at(i).at(j).size();k++) {
                std::cout << res.at(i).at(j).at(k) << " ";
            }
        std::cout << "\n"; 
        }
    std::cout << "\n"; 
    }
    return;
}


int main() {
    // test1();
    // permutationI();
    // permutationII();
    // SubSetSumINaive();
    nQueens(5);
    // SubSetSumII();
    return 0;
}